The present invention relates to systems for securely managing and using cryptographic keys, and more specifically to methods and apparatuses for securing cryptographic devices against external monitoring attacks.
Attackers who gain access to cryptographic keys and other secrets can potentially perform unauthorized operations or forge transactions. Thus, in many systems, such as smartcard-based electronic payment schemes, secrets need to be protected in tamper-resistant hardware. However, recent work by Cryptography Research has shown that smartcards and other devices can be compromised if information about cryptographic secrets leaks to attackers who monitor devices"" external characteristics such as power consumption or electromagnetic radiation.
In both symmetric and asymmetric cryptosystems, secret parameters must be kept confidential, since an attacker who compromises a key can decrypt communications, forge signatures, perform unauthorized transactions, impersonate users, or cause other problems. Methods for managing keys securely using physically secure, well-shielded rooms are known in the background art and are widely used today. However, previously-known methods for protecting keys in low-cost cryptographic devices are often inadequate for many applications, such as those with challenging engineering constraints (cost, size, performance, etc.) or that require a high degree of tamper resistance. Attacks such as reverse-engineering of ROM using microscopes, timing attack cryptanalysis (see, for example, P. Kocher, xe2x80x9cTiming Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems,xe2x80x9d Advances in Cryptologyxe2x80x94CRYPTO""96, Springer-Verlag, pages 104-113), and error analysis (see, for example, E. Biham and A. Shamir, xe2x80x9cDifferential Fault Analysis of Secret Key Cryptosystems,xe2x80x9d Advances in Cryptologyxe2x80x94CRYPTO""97, Springer-Verlag, 1997, pages 513-525) have been described for analyzing cryptosystems.
Key management techniques are known in the background art for preventing attackers who compromise devices from deriving past keys. For example, ANSI X9.24, xe2x80x9cFinancial servicesxe2x80x94retail managementxe2x80x9d defines a protocol known as Derived Unique Key Per Transaction (DUKPT) that prevents attackers from deriving past keys after completely compromising a device""s state. Although such techniques can prevent attackers from deriving old keys, they have practical limitations and do not provide effective protection against external monitoring attacks in which attackers use partial information about current keys to compromise future ones.
Cryptography Research has also developed methods for using iterated hashing operations to enable a client and server to perform cryptographic operations while the client protects itself against external monitoring attacks. In such methods, the client repeatedly applies a cryptographic function to its internal secret between or during transactions, such that information leaked in each of a series of transactions cannot be combined to compromise the secret. However, the system described has a disadvantage in that the server must perform a similar sequence of operations to re-derive the symmetric session key used in each transaction. Thus, in cases such as where there are a large number of unsynchronized server devices (such as electronic cash applications where a large number of merchant terminals operate as independent servers) or if servers have limited memory, the server cannot reliably precompute all possible session keys clients might use. As a result, transaction performance can suffer since a relatively large number of operations may be required for the server to obtain the correct session key. For example, the n-th client session key can require n server operations to derive. A fast, efficient method for obtaining leak-resistant and/or leak-proof symmetric key agreement would thus be advantageous.
The present invention describes ways to make smartcards (and other cryptographic client devices) secure even if attackers are able to use external monitoring (or other) attacks to gather information correlated to the client device""s internal operations. In one embodiment, a cryptographic client device (e.g., a smartcard) maintains a secret key value as part of its state. The client can update its secret value at any time, for example before each transaction, using an update process that makes partial information that may have previously leaked to attackers about the secret no longer (or less) usefully describe the new updated secret value. (Information is considered useful if it can help or enable an attacker to implement an actual attack.) Thus, the secret key value is updated sufficiently frequently (perhaps as often as once per transaction) such that information leaked about the input state does not as usefully describe the updated state. By repeatedly applying the update process, information leaking during cryptographic operations that is collected by attackers rapidly becomes obsolete. Thus, such a system can remain secure against attacks involving repeated measurements of the device""s power consumption or electromagnetic characteristics, even when the system is implemented using leaky hardware and software (i.e., that leak information about the secret values). (In contrast, traditional systems use the same secret value repeatedly, enabling attackers to statistically combine information collected from a large number of transactions.)
The present invention can be used in connection with a client and server using such a protocol. To perform a transaction with the client, the server obtains the client""s current transaction counter (or another key index value). The server then performs a series of operations to determine the sequence of transformations needed to re-derive the correct session key from the client""s initial secret value. These transformations are then performed, and the result is used as a transaction session key (or used to derive a session key).
The present invention can include a sequence of client-side updating processes that allow for significant improvements in the performance of the corresponding server operations, while maintaining leak-resistant and/or leak-proof security characteristics in the client device. In one embodiment of the invention, each process in the sequence is selected from among two forward cryptographic transformations (FA and FB) and their inverses (FAxe2x88x921 and FBxe2x88x921). Using methods that will be described in detail below, such update functions are applied by the client in a sequence that assures that any single secret value is never used or derived more than a fixed number of times (for example, three). Furthermore, the update functions and sequence also assure that the state of (and hence the secret session key value used in) any transaction is efficiently derivable from a starting state (such as the state used in the first transaction) within a small number of applications of FA and FB (or their inverses).
If the number of operations that can securely be performed by a client is n (i.e., n different transactions can be performed, without using the same secret value more than a fixed number of times), a server knowing or capable of obtaining the client""s initial secret value K (or initial state corresponding thereto) can derive any resulting secret value (or corresponding state) in the series of transactions significantly faster than by performing n corresponding updates. Indeed, the state for any given transaction can often be derived by a server using O(log n) calculations of FA and FB (or their inverses). If the system designer has made n sufficiently large, this can allow a virtually limitless set of transactions to be performed by clients while providing excellent server performance.